This invention relates to automatic reclamation of allocated, but unused memory, or garbage, in a computer system that uses a space-incremental garbage collector to collect an object space concurrently with the operation of non-collection threads. Memory reclamation may be carried out by a special purpose garbage collection algorithm that locates and reclaims memory which is unused, but has not been explicitly de-allocated. There are many known garbage collection algorithms, including reference counting, mark-sweep, mark-compact and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms for Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996.
However, many of the aforementioned garbage collection techniques often lead to long and unpredictable delays because normal processing must be suspended during the garbage collection process (called “stop the world” or STW processing) and these collectors scan the entire heap. The garbage collection process is performed by collection threads that perform collection work when all other threads are stopped. Non-collection threads perform tasks for the application. Therefore, they are generally not suitable in situations, such as real-time or interactive systems, where non-disruptive behavior is of greatest importance. Conventional generational collection techniques alleviate these delays somewhat by concentrating collection efforts on small memory areas, called “young” generations in which most of the activity occurs. This concentration reduces the need for collecting the remaining large memory area, called the “old” or “mature” generation and, thus, reduces the time consumed during garbage collection, but does not eliminate it.
When the mature generation is eventually collected, many generational techniques lead to pauses in normal operation which, while less frequent, are still highly disruptive. One approach to eliminate these long pauses is to apply a space-incremental technique to regions in the heap containing older objects. Space-incremental collection techniques allow a subset of objects in the heap to be collected and evacuated independently of the rest of the heap. A given subset consists of one or more possibly noncontiguous regions and forms the collection-set. Examples of such techniques include the Train algorithm as described in “Incremental Collection of Mature Objects”, R. L. Hudson, J. E. B. Moss, Proceedings of the International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, St. Malo, France, pp 388-403, 1992, Springer-Verlag, London, Great Britain; the Garbage-first algorithm as described in “Garbage-First Garbage Collection”, D. Detlefs, C. Flood, S. Heller, A. Printezis, Proceedings of the 4th International Symposium on Memory Management, pp 37-48, 2004 and other techniques allowing partial compaction of the heap as described in “An Algorithm for Parallel Incremental Compaction”, O. Ben-Yitzhak, I. Goft, E. K. Kolodner, K. Kuiper, V. Leikehman, Proceedings of the 3rd International Symposium on Memory Management, pp 100-105, 2002.
As an example, the Train algorithm divides the generation's memory into a number of fixed-sized regions, or car sections. The algorithm associates a car structure with each car section to manage information about the state of that car section. It further orders the car structures in a two-level ordering. During at least some of the collection pauses, one or more of the cars lowest in the overall order are collected; these form the collection-set. Using this ordering and careful placement policies, the algorithm allows the size of collection-sets to be bounded to achieve acceptable pause times even as it guarantees that unreachable data structures too large to fit into a collection-set will be isolated in single trains, and once there, reclaimed as a group. Incremental collectors, such as the Train algorithm, are attractive because they reduce the delays inherent in the collection process. In addition, they are suitable for concurrent garbage collection systems in which collection is performed concurrently with the application by at least one concurrent thread or by different processors in a multiprocessor system.
During the operation of the algorithm, objects in a car may be evacuated, or relocated, to other cars. When an object is relocated, references to that object located outside of the collection region must be changed to point to the new object location. To facilitate the step of finding the references to objects in a region, many space-incremental collectors use “remembered sets.” In particular, a remembered set is associated with each region and tracks memory locations containing references that point to objects in that region. Memory locations are used instead of the references themselves because remembered sets are built over time so that when the time arrives to use the references they may be stale (no longer point to objects in a region associated with that remembered set). Remembered sets may be implemented with various data structures that can be used to represent a set, such as sets, bitmaps, hash tables and bags.
When objects are evacuated from regions in the collection set, the remembered sets associated with those regions are scanned to locate references to the objects so that the references can be updated. In addition, the evacuated objects are scanned in their new locations and their references to objects in other regions or generations are duly recorded in the appropriate remembered sets or data structures.
Since non-collection threads are generally suspended during collection using space-incremental collectors, the collectors can still introduce considerable delays during the collection process. One of the largest sources of these delays is the time taken to scan the remembered sets, because the sets can be quite large and all references must be scanned.
In order to reduce the delays caused by scanning remembered sets one technique scans the remembered sets mostly concurrently with the operation of the non-collection threads. For example, remembered sets can be scanned in a two-phase process. In the first phase, which is performed mostly concurrently with the operation of the non-collection threads, remembered sets are updated when a reference location is modified by the non-collection threads or by the collector (unless the reference is located in a region that will be collected before the region associated with the remembered set) and the remembered set entries are scanned, summarized and partially sorted into associated reference location lists. Then, at the start of the second phase, which is carried out when the non-collection threads are suspended, any remaining remembered set entries for regions in the collection set are scanned and added to the appropriate reference location lists and any remaining unrecorded modifications to the reference locations are recorded. Thereafter, each reference location list is traversed to update the remembered set entries corresponding to evacuated objects.
However, even with the aforementioned technique, remembered sets may still grow large enough to cause significant delays during the updating and scanning process.